In 3D computer graphics, the 3D surface of an object can be developed by a mathematical representation, the output of which is called a 3D model. A 3D model may comprise a plurality of components. FIG. 1 is an exemplary diagram showing a 3D castle model. As shown in FIG. 1, the castle model as a whole could be referred to as the mentioned 3D model which comprises a plurality of components, such as structures of a pillar, tower, window, etc. It can be appreciated that both the 3D model and the component can be in a hierarchical structure. In that case, there are different levels of 3D model and its corresponding components.
In practical applications, such as 3D games, virtual chatting room, digital museum, and CAD, many 3D models consist of a large number of connected components. These multi-connected 3D models usually contain a non-trivial amount of repetitive structures via various transformations. In the castle model shown in FIG. 1, the structure of a pillar is reproduced multiple times on the walls of each of the four towers. The basic structure of the pillar is shown at the lower right of FIG. 1. In addition, each tower itself comprises a repetitive structure illustrated by the lower left part of FIG. 1. Depending on its position, this basic tower structure is complemented with smaller structures such as some of the windows placed on the roofs. In this sense, the tower structure is a connected component which comprises one or more repetitive structures. It can be appreciated that some of the repetitive structures can also be hierarchical.
An efficient compression method for this kind of 3D models enables to explore the repetitive structures and extract the redundancy to achieve a high compression ratio.
Pattern-based 3D Model Compression (PB3DMC) codec, which is an efficient compression algorithm for multi-connected 3D models, was proposed by taking advantage of discovering repetitive structures in input 3D models. Repetitive structures of a 3D model are discovered in various positions, orientations, and scaling factors. The 3D model is then organized into “pattern-instance” representation. A pattern is used to denote a representative geometry of a corresponding repetitive structure. Components belonging to a repetitive structure are denoted as instances of the corresponding pattern and may be represented by a pattern ID and transformation information, for example, reflection, translation, rotation and possible scaling with respect to the pattern. The instance transformation information may be organized into, for example, reflection part, translation part, rotation part, and possible scaling part. There might be some components of the 3D models that are not repetitive, which are referred to as unique components. The instances can be represented by a pattern ID and an instance transformation matrix, which may include information on reflection, scaling, rotation and translation etc. It can be appreciated that an instance component can be completely recovered from the instance transformation matrix and the corresponding pattern, which can be retrieved using the pattern ID. Thus, when compressing an instance component, it is equivalent to compress the pattern ID and the instance transformation matrix.
PB3DMC has been presented to MPEG-3DGC since the 95th MPEG meeting and received quite positive feedback. The bitstream syntax and semantics of PB3DMC has been proposed to MPEG-3DGC in the 97th, 98th and 99th MPEG meeting. From the 97th MPEG meeting to the 100th MPEG meeting, PB3DMC is part of 3DG Core Experiment (CE). Starting from the 101th MPEG meeting, PB3DMC is moving from Core Experiment (CE) to Working Draft (WD).
In 3D model compression, some components or some parts of components of a 3D model may need to be allocated with a number of bits for the mathematical representation. For example, in the codec of the repetitive structure discovery based 3D model compression, a number of bits might be need to be allocated to the reflection, scaling, rotation and translation parts of an instance component and unique components of a 3D model. An efficient bit allocation scheme is an important topic for designing a 3D model codec.